package com.LeeCode;

/**
 * 等积子集的划分方案
 */

public class Code3566 {
    public static void main(String[] args) {
        int[] nums = {4};
        int target = 2;
        System.out.println(new Code3566().checkEqualPartitions(nums, target));
    }

    public boolean checkEqualPartitions(int[] nums, long target) {
        int n = nums.length;

        long product = 1;
        for (int i = 0; i < n; i++) {
            product *= nums[i];
        }
        if (product != target * target) return false;

        return dfs(nums, 0, 0, 1, target);
    }

    private boolean dfs(int[] nums, int index, int size, long cur, long target) {
        if (index >= nums.length) return false;
        if (cur == target && 0 < size && size < nums.length) {
            return true;
        } else if (cur > target) {
            return false;
        }
        boolean noChoose = dfs(nums, index + 1, size, cur, target);
        if (noChoose) return true;
        boolean choose = dfs(nums, index + 1, size + 1, cur * nums[index], target);
        return choose;
    }
}
